# 树状数组
snippet bit "树状数组" b
/* ======== 树状数组 BIT 
 * 1.单点增减，区间和
 *    1.1 逆序对
 * 2.区间增减，单点值
 * 3.区间增减，区间和
 * 4.单点修改，末尾压入，区间最值
 * */
namespace bit {
    typedef long long ll;
    ll c[maxn],SIZE=maxn;
    ll c2[maxn]; // c2[i] = i*c[i]
    inline void bit_init(){}

    /* 区间和 */
    inline ll lowbit(ll x) { return x & -x;}
    void update(ll pos,ll add){ while(pos<=SIZE) c[pos]+=add,pos+=lowbit(pos);}
    /* 差分,区间增减,单点查询*/
    void update_range(ll l,ll r,ll add){ update(l,add);update(r+1,-add); }
    ll query(int pos){ll sum=0;while(pos>0) sum+=c[pos],pos-=lowbit(pos); return sum;}

    /* 差分,区间增减,区间查询*/
    //核心公式：sum_a[i] = (i+1)×sum_c[i] - sum_{i×c[i]}
    void update_c_c2(ll pos,ll add){ //同时更新c，c2
        ll t = pos; while( pos <= SIZE){ c[pos] += add; c2[pos] += t*add; pos+=lowbit(pos);}
    }
    void update_range_c_c2(ll l,ll r ,ll add){ update_c_c2(l, add);update_c_c2(r+1, -add); }
    ll query2(ll pos){ ll sum = 0; while( pos > 0) sum += c2[pos], pos -=lowbit(pos); return sum; }
    ll query_range_sum(ll l,ll r){ return (r+1)*query(r) - query2(r) - l*query(l-1) + query2(l-1); }

    // ===== 4.单点修改，末尾压入，区间最值
    ll a[maxn]; // 原数组
    void update_by_child(ll pos,ll v){ // alias push
        c[pos] = a[pos] = v;
        ll i,lb = lowbit(pos);
        for(i=1 ; i < lb ; i <<= 1) c[pos] = std::max(c[pos],c[pos-i]);
    }

    void update_ex(ll pos,ll v){
        update_by_child(pos,v); int tmp = c[pos];
        for( pos += lowbit(pos); pos <=SIZE; pos+=lowbit(pos)){
            if( c[pos] < tmp) c[pos] = tmp;
            else break; //没有更新父亲
        }
    }
    ll query_ex(ll l ,ll r){
        ll ex = -1;
        while( l <= r){
            ll left = r - lowbit(r) +1; //范围内的最左点
            if( left >= l) ex = std::max(ex,c[r]) , r = left-1;
            else ex = std::max(ex,a[r]),r--;
        }
        return ex;
    }
}
endsnippet

snippet BIT_2D "二维BIT" b
/* 二维BIT  BIT_2D */
/* 核心在于 C[x][y] 管辖的范围*/
namespace BIT_2D {
    //横管横，纵管纵
    typedef long long ll;
    const int MAXN = 4100;
    int SIZE_N = 4100;
    int SIZE_M = 4100;
    ll a[MAXN][MAXN],c[MAXN][MAXN];
    inline int lowbit(int x){ return x&-x;}
    void update(int x,int y,int val){
        for(int i=x;i <=SIZE_N;i += lowbit(i))
            for(int j=y;j <=SIZE_M;j += lowbit(j))
                c[i][j] += val;
    }
    ll query(int x,int y){
        ll sum =0;
        for( int i = x;i>0; i -= lowbit(i))
            for(int j = y ;j >0;j-=lowbit(j))
                sum += c[i][j];
        return sum;
    }
    ll query_sub_martix(int x1,int y1,int x2,int y2){ return query(x2, y2) - query(x2, y1-1) - query(x1-1,y2) + query(x1-1, y1-1); }
}

endsnippet
